#include "headfiles.h"

using namespace std;

// Input s cannot contain '*' and '.', 
// Input p can have these two chars
/*
bool isStringMatch(const char *s, const char *p) {
    if (*p == '\0') {
        if (*s == '\0') {
            return true;
        }
        else {
            return false;
        }
    }

    // if the next char of p is not a '*'
    if (*(p + 1) != '*') {
        if (*p == *s) {
            return isStringMatch(s + 1, p + 1);
        }

        if (*p == '.' && *s != '\0') {
            return isStringMatch(s + 1, p + 1);
        }
    }

    // the next char of p is '*'
    while ( (*p == *s) || ((*p == '.') && (*s == '\0'))) {
        if (isStringMatch(s, p + 2)) return true;
        s++;
    }

    return isStringMatch(s, p + 2);
}
*/

bool isStringMatch(const char *s, const char *p) {
    int s_size = strlen(s);
    int p_size = strlen(p);

    vector<bool> prev(p_size + 1, false);
    prev[0] = true;

    int i, j;
    for (i = 1; i <= p_size; i++) {
        prev[i] = prev[i - 1] && (p[i - 1] == '*');
    }

    vector<bool> cur(p_size + 1, false);
    for (i = 1; i <= s_size; i++) {
        for (j = 1; j <= p_size; j++) {
            if (p[j - 1] != '*') {
                cur[j] = prev[j - 1] && (p[j - 1] == '?' || p[j - 1] == s[j - 1]);
            }
            else {
                cur[j] = prev[j] || cur[j - 1];
            }
        }
        prev = cur;
    }

    return prev[p_size];
}
